package com.kfm.base.structure;

public class Exer02 {

    public static void main(String[] args) {
    }

    public static void quickSort(Book[] books) {
        if (books == null || books.length < 2) {
            return;
        }
        quickSort(books, 0, books.length - 1);
    }

    private static void quickSort(Book[] books, int start, int end) {
        // 递归结束
        if (start > end) {
            return;
        }

        // 基准值
        int base = books[start].getNo();
//        Book base = books[start];
        // 左边的哨兵
        int left = start;
        // 右边的哨兵
        int right = end;

        while (left < right) {
            // 找右边比基准值小的下标
            while (left < right && books[right].getNo() >= base) {
                right--;
            }
            // 找右边比基准值大的下标
            while (left < right && books[left].getNo() <= base) {
                left++;
            }

            if (left != right) {
                Book book = books[left];
                books[left] = books[right];
                books[right] = book;
            }
        }

        // 交换基准值位置
        Book temp = books[start];
        books[start] = books[left];
        books[left] = temp;

        // 对基准值左边进行快排
        quickSort(books, start, left - 1);
        // 对基准值右边进行快排
        quickSort(books, left + 1, end);
    }
}

class Book {
    private String name;

    private int no;

    public Book(String name, int no) {
        this.name = name;
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }
}
